SherbyNet - /page/wikibook/entry.mu

Micron Document

Second-order cone programming

16.9 KB · ⇊ 11 parts · ⤓ Micron 16.9 KB · ⤓ HTML 82.0 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

A second-order cone program (SOCP) is a convex optimization problem of the form

minimize f T x {\displaystyle \ f^{T}x\ }

subject to ‖ ‖ A i x + b i ‖ ‖ 2 ≤ ≤ c i T x + d i , i = 1 , … … , m {\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i},\quad i=1,\dots ,m} F x = g {\displaystyle Fx=g\ }

where the problem parameters are f ∈ ∈ R n , A i ∈ ∈ R n i × × n , b i ∈ ∈ R n i , c i ∈ ∈ R n , d i ∈ ∈ R , F ∈ ∈ R p × × n {\displaystyle f\in \mathbb {R} ^{n},\ A_{i}\in \mathbb {R} ^{{n_{i}}\times n},\ b_{i}\in \mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^{p\times n}} , and g ∈ ∈ R p {\displaystyle g\in \mathbb {R} ^{p}} . x ∈ ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} is the optimization variable. ‖ ‖ x ‖ ‖ 2 {\displaystyle \lVert x\rVert _{2}} is the Euclidean norm and T {\displaystyle ^{T}} indicates transpose.cite-ref-boyd-1-0[1]

The name "second-order cone programming" comes from the nature of the individual constraints, which are each of the form:

‖ ‖ A x + b ‖ ‖ 2 ≤ ≤ c T x + d {\displaystyle \lVert Ax+b\rVert _{2}\leq c^{T}x+d}

These each define a subspace that is bounded by an inequality based on a second-order polynomial function defined on the optimization variable x {\displaystyle x} ; this can be shown to define a convex cone, hence the name "second-order cone".cite-ref-2[2] By the definition of convex cones, their intersection can also be shown to be a convex cone, although not necessarily one that can be defined by a single second-order inequality. See below for a more detailed treatment.

SOCPs can be solved by interior point methodscite-ref-3[3] and in general, can be solved more efficiently than semidefinite programming (SDP) problems.cite-ref-fawzi-4-0[4] Some engineering applications of SOCP include filter design, antenna array weight design, truss design, and grasping force optimization in robotics.cite-ref-0-5-0[5] Applications in quantitative finance include portfolio optimization; some market impact constraints, because they are not linear, cannot be solved by quadratic programming but can be formulated as SOCP problems.cite-ref-6[6]cite-ref-7[7]cite-ref-8[8]

Contents

• Second-order cones

• Relation with other optimization problems

• Examples

• Quadratic constraint

• Stochastic linear programming

• Stochastic second-order cone programming

• Other examples

• Solvers and scripting (programming) languages

• See also

• References

Second-order cones

The standard or unit second-order cone of dimension n + 1 {\displaystyle n+1} is defined as

C n + 1 = { [ x t ] | x ∈ ∈ R n , t ∈ ∈ R , ‖ ‖ x ‖ ‖ 2 ≤ ≤ t } {\displaystyle {\mathcal {C}}_{n+1}=\left\{{\begin{bmatrix}x\\t\end{bmatrix}}{\Bigg |}x\in \mathbb {R} ^{n},t\in \mathbb {R} ,\|x\|_{2}\leq t\right\}} .

The second-order cone is also known by the names quadratic cone or ice-cream cone or Lorentz cone. For example, the standard second-order cone in R 3 {\displaystyle \mathbb {R} ^{3}} is

{ ( x , y , z ) | x 2 + y 2 ≤ ≤ z } {\displaystyle \left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}} .

The set of points satisfying a second-order cone constraint is the inverse image of the unit second-order cone under an affine mapping:

‖ ‖ A i x + b i ‖ ‖ 2 ≤ ≤ c i T x + d i ⇔ ⇔ [ A i c i T ] x + [ b i d i ] ∈ ∈ C n i + 1 {\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}A_{i}\\c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_{i}+1}}

and hence is convex.

The second-order cone can be embedded in the cone of the positive semidefinite matrices since

| | x | | ≤ ≤ t ⇔ ⇔ [ t I x x T t ] ≽ ≽ 0 , {\displaystyle ||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,}

i.e., a second-order cone constraint is equivalent to a linear matrix inequality. The nomenclature here can be confusing; here M ≽ ≽ 0 {\displaystyle M\succcurlyeq 0} means M {\displaystyle M} is a semidefinite matrix: that is to say

x T M x ≥ ≥ 0 for all x ∈ ∈ R n {\displaystyle x^{T}Mx\geq 0{\text{ for all }}x\in \mathbb {R} ^{n}}

which is not a linear inequality in the conventional sense.

Similarly, we also have,

‖ ‖ A i x + b i ‖ ‖ 2 ≤ ≤ c i T x + d i ⇔ ⇔ [ ( c i T x + d i ) I A i x + b i ( A i x + b i ) T c i T x + d i ] ≽ ≽ 0 {\displaystyle \lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}(c_{i}^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_{i}\end{bmatrix}}\succcurlyeq 0} .

Relation with other optimization problems

When A i = 0 {\displaystyle A_{i}=0} for i = 1 , … … , m {\displaystyle i=1,\dots ,m} , the SOCP reduces to a linear program. When c i = 0 {\displaystyle c_{i}=0} for i = 1 , … … , m {\displaystyle i=1,\dots ,m} , the SOCP is equivalent to a convex quadratically constrained linear program.

Convex quadratically constrained quadratic programs can also be formulated as SOCPs by reformulating the objective function as a constraint.cite-ref-0-5-1[5] Semidefinite programming subsumes SOCPs as the SOCP constraints can be written as linear matrix inequalities (LMI) and can be reformulated as an instance of semidefinite program.cite-ref-0-5-2[5] The converse, however, is not valid: there are positive semidefinite cones that do not admit any second-order cone representation.cite-ref-fawzi-4-1[4]

Any closed convex semialgebraic set in the plane can be written as a feasible region of a SOCP,.cite-ref-9[9] However, it is known that there exist convex semialgebraic sets of higher dimension that are not representable by SDPs; that is, there exist convex semialgebraic sets that can not be written as the feasible region of a SDP (nor, a fortiori, as the feasible region of a SOCP).cite-ref-10[10]

Examples

Quadratic constraint

Consider a convex quadratic constraint of the form

x T A x + b T x + c ≤ ≤ 0. {\displaystyle x^{T}Ax+b^{T}x+c\leq 0.}

This is equivalent to the SOCP constraint

‖ ‖ A 1 / 2 x + 1 2 A − − 1 / 2 b ‖ ‖ ≤ ≤ ( 1 4 b T A − − 1 b − − c ) 1 2 {\displaystyle \lVert A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}b-c\right)^{\frac {1}{2}}}

Stochastic linear programming

Consider a stochastic linear program in inequality form

minimize c T x {\displaystyle \ c^{T}x\ }

subject to P ( a i T x ≤ ≤ b i ) ≥ ≥ p , i = 1 , … … , m {\displaystyle \mathbb {P} (a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m}

where the parameters a i {\displaystyle a_{i}\ } are independent Gaussian random vectors with mean a ¯ ¯ i {\displaystyle {\bar {a}}_{i}} and covariance Σ Σ i {\displaystyle \Sigma _{i}\ } and p ≥ ≥ 0.5 {\displaystyle p\geq 0.5} . This problem can be expressed as the SOCP

minimize c T x {\displaystyle \ c^{T}x\ }

subject to a ¯ ¯ i T x + Φ Φ − − 1 ( p ) ‖ ‖ Σ Σ i 1 / 2 x ‖ ‖ 2 ≤ ≤ b i , i = 1 , … … , m {\displaystyle {\bar {a}}_{i}^{T}x+\Phi ^{-1}(p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m}

where Φ Φ − − 1 ( ⋅ ⋅ ) {\displaystyle \Phi ^{-1}(\cdot )\ } is the inverse normal cumulative distribution function.cite-ref-boyd-1-1[1]

Stochastic second-order cone programming

We refer to second-order cone programs as deterministic second-order cone programs since data defining them are deterministic. Stochastic second-order cone programs are a class of optimization problems that are defined to handle uncertainty in data defining deterministic second-order cone programs.cite-ref-11[11]

Other examples

Other modeling examples are available at the MOSEK modeling cookbook.cite-ref-12[12]

Solvers and scripting (programming) languages

| Name | License | Brief info |

|---|---|---|

| ALGLIB | free/commercial | A dual-licensed C++/C#/Java/Python numerical analysis library with parallel SOCP solver. |

| AMPL | commercial | An algebraic modeling language with SOCP support |

| Artelys Knitro | commercial | |

| CPLEX | commercial | |

| FICO Xpress | commercial | |

| Gurobi Optimizer | commercial | |

| MATLAB | commercial | The coneprog function solves SOCP problems [ 13 ] using an interior-point algorithm [ 14 ] |

| MOSEK | commercial | parallel interior-point algorithm |

| NAG Numerical Library | commercial | General purpose numerical library with SOCP solver |